package oct2013;

import java.util.HashMap;

/**
 * @author Yinzi Chen
 * @date Nov 10, 2013
 */
public class LRUCache {
    class LRUEntry {
        int key;
        int value;
        LRUEntry next;
        LRUEntry prev;

        public LRUEntry(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private HashMap<Integer, LRUEntry> cache;
    private LRUEntry head;
    private LRUEntry tail;

    public LRUCache(int capacity) {
        cache = new HashMap<Integer, LRUEntry>();
        head = new LRUEntry(0, 0);
        tail = head;
        for (int i = 0; i < capacity; ++i) {
            tail.next = new LRUEntry(0, 0);
            tail.next.prev = tail;
            tail = tail.next;
        }
        tail.next = head;
        head.prev = tail;
    }

    public int get(int key) {
        LRUEntry entry = cache.get(key);
        if (entry != null) {
            detach(entry);
            attach(entry);
            return entry.value;
        }
        return -1;
    }

    public void set(int key, int value) {
        LRUEntry entry = cache.get(key);
        if (entry == null) {
            entry = head.next;
            detach(entry);
            cache.remove(entry.key);
            entry.key = key;
            cache.put(key, entry);
        } else {
            detach(entry);
        }
        entry.value = value;
        attach(entry);
    }

    private void detach(LRUEntry entry) {
        entry.prev.next = entry.next;
        entry.next.prev = entry.prev;
        if (entry == tail) {
            tail = entry.prev;
        }
    }

    private void attach(LRUEntry entry) {
        entry.next = head;
        tail.next = entry;
        entry.prev = tail;
        head.prev = entry;
        tail = entry;
    }

    public static void main(String[] args) {
        LRUCache a = new LRUCache(1);
        a.set(2, 1);
        System.out.println(a.get(2));
        a.set(3, 2);
        System.out.println(a.get(2));
    }
}
